第4章 字典

字典又称符号表(symbol table), 关联数组(associative array), 映射(map), 是一种用于保存键值对的数据结构. 字典中的每个键都是独一无二的.

Redis的数据库就是使用字典来作为底层实现的, 对数据库的增删查改操作都是构建在对字典的操作之上.

4.1 字典的实现

Redis的字典使用哈希表作为底层实现

• dictType提供了一簇用于操作特定类型键值对的函数, privdata则保存了需要传给那些类型特定函数的可选参数
• ht属性包含两个哈希表, 一般只使用ht[0], 只有在rehash时使用ht[1]

4.2 哈希算法

hash = dict->type->hashFunction(key); 
index = hash & dict->ht[x].sizemask; // 使用sizemask和哈希值计算出索引值

redis使用MurmurHash2算法来计算键的哈希值

4.3 解决键冲突

当有两个及以上的键被分配到了哈希表的同一个索引上时, 称发生了冲突(collision)

Redis的哈希表使用链地址法(separate chaining)来解决键冲突, 每个哈希表节点都有一个next指针, 同一个索引上的多个节点存储为单向链表.

4.4 rehash

当哈希表保存的键值对数量太多或太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩:

1. 依据ht[0].used为ht[1]分配空间, 扩展时, 大小为第一个大于等于used*2的2^n; 收缩时, 大小为第一个大于等于used的2^n

2. 将ht[0]的全部键值对迁移到ht[1]

3. 释放ht[0], 将ht[1]设置为ht[0], 并为ht[1]新建一个空白哈希表

rehash的自动触发条件与负载因子有关:

// 负载因子 = 已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size;

• 服务器目前没有执行BGSAVE或BGREWRITEAOF命令, 且负载因子≥1, 自动扩展
• 正在执行BGSAVE或BGREWRITEAOF命令, 但负载因子≥ 5, 自动扩展
• 负载因子小于0.1, 自动收缩

4.5 渐进式rehash

为了避免rehash对服务器性能造成影响, 服务器不是一次性迁移所有键值对, 而是分多次, 渐进式的.

• 在渐进式rehash期间, 会同时使用ht[0]和ht[1]

  • 查找和更新操作会先查询ht[0], 没找到则再查询ht[1]

  • 新增键值对会直接保存到ht[1]

4.6 字典API